1644D - Cross Coloring - CodeForces Solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <stack>
#include <set>
#include <string>
#include <cctype>
#include <numeric>
#include <string>
#include <climits>
#include <bitset>
#include <chrono>
 
using namespace std;
 
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " ";  _print(x); cerr << endl;
#else
#define debug(x)
#endif
 
#define ll long long int
#define vint vector<int>
#define vlong vector<ll>
#define mod1 1000000007
#define mod2  998244353
#define pi 3.141592653589793238462643
#define loop(i,a,b) 	for(int i=(a);i<=(b);i++)
#define looprev(i,a,b) 	for(int i=(a);i>=(b);i--)
#define all(x)  x.begin(), x.end()
#define iint(n) int n; cin >> n;
#define ill(n) ll n; cin >> n;
#define istr(n) string n; cin >> n;
#define print(n) cout << (n) << endl
#define prll(n) cout << (n) << endl
#define prstr(s) cout << (s) << endl
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define mp make_pair
#define vpii vector<pii>
#define vpll vector<pll>
#define vstr vector<string>
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define getSet(x) __builtin_popcountll(x)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); 

#define sz(v) (int) v.size()
#define ivec1(v,n) vint v; loop(_,0,n-1) {iint(___); v.pb(___);}
#define input1(v,n) loop(_,0,n-1) {iint(___); v.pb(___);}
#define ivec2(v,n) vlong v; loop(_,0,n-1) {ill(___); v.pb(___);}
#define input2(v,n) loop(_,0,n-1) {ill(___); v.pb(___);}
#define prvec(arr,n) loop(_,0,n-1){ cout << arr[_] << " ";} cout << endl;
#define vsort(vc) sort(all(vc))
#define vrsort(vc) sort(vc.rbegin(),vc.rend())
 
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
// void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
// void _print(ull t) {cerr << t;}
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

//set in decreasing order
/*
auto cmp = [](pii const &x, pii const &y) {
            return x > y;
};
set<pii, decltype(cmp)> v(cmp);

bool cmp(pair<string,int> p1,pair<string,int> p2){
    if (p1.ss != p2.ss)
        return p1.ss > p2.ss;
    return p1.ff < p2.ff;
}
remove all consecutive duplicacy
v.erase(unique(all(v)),v.end());
count unique;
distance(v.begin(),unique(all(v)));
*/
//-------------------------------------------------------------------------------------------------

void solve(){
    ll n,m,k,q; cin >> n >> m >> k >> q;
    vpll v;
    loop(i,0,q-1){
        ill(a);ill(b);
        v.pb(mp(a,b));
    }
    set<ll> row,col;
    row.insert(v[q-1].ff);col.insert(v[q-1].ss);
    ll ans = k;
    looprev(i,q-2,0){
        debug(row); debug(col); debug(ans);
        if (sz(row) == n || sz(col) == m)
            break;
        ll a = v[i].ff,b =v[i].ss;
        if (row.find(a) == row.end() || col.find(b) == col.end())
            ans = (ans*k)%mod2;
        row.insert(a); col.insert(b);
    }
    print(ans);
}       

//-------------------------------------------------------------------------------------------------
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("Error.txt","w",stderr);
    auto start_time = chrono::steady_clock::now();
#endif   
    int t; t = 1; 
    cin >> t;
    // preComp();
    while(t--)
        solve();
        
#ifndef ONLINE_JUDGE
    auto end_time = chrono::steady_clock::now();
    auto diff_time = end_time - start_time;
    cout << "Execution time : " << fixed << setprecision(5) <<  chrono::duration <double, milli> (diff_time).count() << " ms" << endl;
#endif
    return 0;
}